package likou.offer2;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;

/**
 * 给定一个只包含数字的字符串 s ，用以表示一个 IP 地址，返回所有可能从 s 获得的 有效 IP 地址 。你可以按任何顺序返回答案。
 * 有效 IP 地址 正好由四个整数（每个整数位于 0 到 255 之间组成，且不能含有前导 0），整数之间用 '.' 分隔。
 * 例如："0.1.2.201" 和 "192.168.1.1" 是 有效 IP 地址，但是 "0.011.255.245"、"192.168.1.312" 和 "192.168@1.1" 是 无效 IP 地址。
 * 链接：https://leetcode-cn.com/problems/0on3uN
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2021/10/01 11:52
 */
public class _087 {
    public static void main(String[] args) {
        _087 o = new _087();
        System.out.println(o.restoreIpAddresses("25525511135"));
    }

    List<String> res = new ArrayList<>();
    char[] buf;
    public List<String> restoreIpAddresses(String s) {
        if(s.length() > 12 || s.length() < 4) return Collections.emptyList();
        char[] chars = s.toCharArray();
        buf = new char[chars.length + 4];
        backtrack(chars, 0, 0);

        return res;
    }

    private void backtrack(char[] chars, int k, int p) {
        if (k == 4 && p == chars.length) {
            res.add(new String(buf, 0, chars.length + 3));
        }

        if (k == 4 && p < chars.length) return;
        for (int i = p; i < chars.length && i < p + 3; i++) {
            buf[i + k] = chars[i];
            buf[i + k + 1] = '.';
            if (isValid(chars, p, i)) backtrack(chars, k + 1, i + 1);
            else break;
        }
    }

    private boolean isValid(char[] chars, int s, int e) {
        int len = e - s + 1;
        if (chars[s] == '0') return len == 1;
        int d = 0;
        for (int k = s; k <= e; k++) {
            d = d * 10 + (chars[k] - '0');
        }
        return d <= 255;
    }
}
